/*https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/submissions/567370783/*/

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        //由于船的最低运载能力呈现出一个单调性 因此可以使用二分
        //由于船的最低运载能力至少需要大于最重的包裹 而最高也不会超过所有包裹的总重量 因此我们可以确定二分搜索的左右边界
        
        //int l = *max_element(weights.begin(), weights.end()), r = accumulate(weights.begin(), weights.end(), 0);
        //sort(weights.begin(),weights.end());
        int sum = 0;
        int max = 0;
        for(int x :weights){
            sum += x;
            if(x > max)max = x;
        }
        int l = max;
        int r = sum;
        while(l < r){
            int mid = l + (r-l)/2;
            int day = 1,temp = 0;//至少是需要一天的
            for(int w : weights){
                if(temp + w > mid){
                    day++;//需要再多一天来运输
                    temp = 0;//当天的总运载重量置为0 
                }
                temp += w;

            }
            if(day <= days){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l;
    
    }
};